有一些演算法是在圖(graph)上操作，我們可以先想一些實際的例子，例如：

• 開車的時候，使用導航系統找到最短路徑抵達目的地。

• 下棋的程式知道如何利用最少的步數獲勝。

• 如果有很多代辦事項，其中某些事又必須優先處理，我們可能需要將所有事情合理排序。

應該大部分人都有這些例子的親身經驗，而這些例子都可以想成圖的關係。不只在科學中，圖在生活中也有非常多應用，所以有許多相關、實用的演算法。當然在看演算法之前，先來大致了解一下圖是什麼。

圖

圖是用來表示物體與物體之間關係的結構。圖由兩個部分組成：節點(node或vertex)代表物體，邊(edge)代表節點之間的關係。例如下方的圖就有六個節點和七條邊。

另外圖中也可能會有環(cycle)，也就是第一個節點和最後一個節點重複的結構，例如圖中的1-2-5-1即形成一個環。

看到這裡可能會聯想到也是由節點組成的樹結構。沒錯，樹也是圖的一種，它的特性是每個子節點只會有一個父節點，且沒有環的結構(樹只會往下生長，子節點不會回頭指向父節點)。

另外，圖可以分為無向圖(undirected graph)和有向圖(directed graph)。無向圖的邊沒有方向性(如上圖)，代表關係是雙向的，沒有方向上的區別，例如聚會上如果毛豆和大雄握過手，當然也就代表的大雄跟毛豆握過手。

有向圖的邊則會有箭頭來表示出方向性，代表關係是單向的，例如毛豆欠大雄100塊，不代表大雄一定欠毛豆錢，所以圖上的表達可以是毛豆有單向的箭頭指向大雄。

有了這樣基本的認識，可以開始解決一些問題。而看到圖我們最先想解決的可能是尋找路徑的問題。

最短路徑問題

假設同樣是上方的圖，我們想要找到從6到1的最短路徑，也就是經過最少段邊的路徑。因此我們的作法是從6出發，每到一個節點都檢查看能不能到達1：

從6可以到1嗎？不行，它可以直接到達的地方是4。

從4可以到1嗎？不行，它可以直接到達的地方是5和3。

從5可以到1嗎？可以，所以最短的路徑是6-4-5-1。

雖然感覺好像什麼都沒做，只是走向終點，但這樣尋找最短路徑的方法叫做廣度優先搜尋(breadth-first search, BFS)。這種演算法會搜尋一個圖中所有節點，它可以用來找出某目標是否在圖中，或者節點A到節點B的最短路徑，它的作法是：

1. 將一個節點放入佇列(queue)中。

2. 檢查佇列的第一個節點是否為目標，

   如果是，結束搜尋；

   如果不是，將所有與它相連的節點放入佇列中。

以剛剛的例子來說，我們一開始將6放進佇列中，6不是目標，所以將相鄰的節點4放進佇列中；接著檢查4也不是目標，所以將與4相鄰的節點5, 3放入佇列，再逐一檢查。廣度優先搜尋就會如此一直檢查下去，直到找到目標或所有節點都被檢查完。

這樣的步驟可能讓人想問，剛剛是因為先檢查5，所以找到了最短路徑，但如果4之後變成先檢查3，就會繞遠路嗎？

答案是不會，而這也跟步驟中特別強調使用「佇列」有很大關係。

下一回我們會看到佇列的特性，以及它如何確保廣度優先搜尋的正確性。